#include "dlist.h"

typedef struct DListElmt_tag{
	void*			data;

	DListElmt*		next;
	DListElmt*		prev;
}DListElmt;

typedef struct DList_tag{
	int size;

	int (*match)(const void* key1, const void* key2);
	void (*destroy)(void* data);

	DListElmt* head;
	DListElmt* tail;
}DList;

DList* dlist_create(void (*destroy)(void* data))
{
	DList* list;
	assert(NULL != (list=(DList* )malloc(sizeof(DList))));
	assert(NULL != destroy);
	
	list->size = 0;
	
	list->head = NULL;
	list->tail = NULL;

	list->destroy = destroy;

	return list;
}
void dlist_destroy(DList* list)
{
	void* data;
	assert(NULL != list);
	assert(NULL != list->destroy);

	while(list->size > 0)
	{
		/* remove the head of the list */
		if (dlist_rmv(list, NULL, &data)==0)
		{
			list->destroy(data);
		}
	}
	free(list);
	list = NULL;
}

int dlist_ins_prev(DList* list, \
				   DListElmt* element, const void* data)
{
	DListElmt* new_element;
	assert(NULL != list);
	assert(NULL != (new_element=(DListElmt* )malloc(sizeof(DListElmt))));
	
	new_element->data = (void* )data;

	if (list->size == 0)		//empty list
	{
		new_element->next = NULL;
		new_element->prev = NULL;
		list->head = new_element;
		list->tail = new_element;
	} 
	else
	{
		assert(NULL != element);
		new_element->next = element;
		new_element->prev = element->prev;
		if (dlist_is_head(list,element))	//insert before head
		{
			list->head->prev = new_element;
			list->head = new_element;
		} 
		else								//or other
		{
			element->prev = new_element;
			element->prev->next = new_element;
		}
		
	}
	list->size++;
	return 0;
}

int dlist_ins_next(DList* list, \
				   DListElmt* element,const void* data)
{
	DListElmt* new_element;
	assert(NULL != list);
	assert(NULL != (new_element=(DListElmt* )malloc(sizeof(DListElmt))));
	
	new_element->data = (void* )data;

	if (list->size == 0)			//empty list
	{
		new_element->next = NULL;
		new_element->prev = NULL;
		list->head = new_element;
		list->tail = new_element;
	}
	else
	{
		assert(NULL != element);
		new_element->prev = element;
		new_element->next = element->next;
		if (dlist_is_tail(element))		//insert after tail
		{
			list->tail->next = new_element;
			list->tail = new_element;
		}
		else							//or other
		{
			element->next = new_element;
			element->next->prev = new_element;
		}	
	}

	list->size++;
	return 0;
}

int dlist_rmv(DList* list, \
			  DListElmt* element, void** data)
{
	assert(NULL != list && list->size > 0);
	assert(NULL != element);
	*data = element->data;

	if (dlist_is_head(list,element))
	{
		list->head = list->head->next;
		if (NULL == list->head)
			list->tail = NULL;		//just one element
		else
			list->head->prev = NULL;	//or other element
	} 
	else
	{
		element->prev->next = element->next;
		if (dlist_is_tail(element))		//the element to be removed is tail
			list->tail = element->prev;
		else
			element->next->prev = element->prev; //or other element
	}
	
	free(element);
	list->size--;
	return 0;
}

int dlist_size(const DList* list)
{
	return list->size;
}
DListElmt* dlist_head(const DList* list)
{
	return list->head;
}
DListElmt* dlist_tail(const DList* list)
{
	return list->tail;
}
int dlist_is_head(const DList* list, \
				  const DListElmt* element)
{
	return (element == list->head ? 1 : 0 );
}
int dlist_is_tail(const DListElmt* element)
{
	return (element->next == NULL ? 1 :0 );
}

void* dlist_data(const DListElmt* element)
{
	return element->data;
}
DListElmt* dlist_next(const DListElmt* element)
{
	return element->next;
}
DListElmt* dlist_prev(const DListElmt* element)
{
	return element->prev;
}
